

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Cheney">
  <meta name="keywords" content="Coding">
  
    <meta name="description" content="LR(0)、SLR、LR、LALR 的区别与判断方法。翻译程序、编译程序、解释程序。根据正则表达式写出对应的最小化的DFA。判断给定文法是不是LL（１）的，若是，则给出预测分析表并给出识别输入串的过程。等">
<meta property="og:type" content="article">
<meta property="og:title" content="编译原理复习总结（精华版）">
<meta property="og:url" content="https://cheney822.gitee.io/2021/05/09/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86__%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86%E5%A4%8D%E4%B9%A0%E6%80%BB%E7%BB%93%EF%BC%88%E7%B2%BE%E5%8D%8E%E7%89%88%EF%BC%89/index.html">
<meta property="og:site_name" content="Cheney blog">
<meta property="og:description" content="LR(0)、SLR、LR、LALR 的区别与判断方法。翻译程序、编译程序、解释程序。根据正则表达式写出对应的最小化的DFA。判断给定文法是不是LL（１）的，若是，则给出预测分析表并给出识别输入串的过程。等">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/20210511114109555-20220405205526898.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/20210511114126577-20220405205526972.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/20210509210934937-20220405205527164.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/20210510080444695-20220405205527238.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/20210510080500270-20220405205527394.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/2021051008045345-20220405205527497.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/20210510080511237-20220405205527622.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/2021051309313828-20220405205527662.jpg">
<meta property="article:published_time" content="2021-05-09T00:22:00.000Z">
<meta property="article:modified_time" content="2022-04-05T13:14:27.207Z">
<meta property="article:author" content="Cheney">
<meta property="article:tag" content="笔记">
<meta property="article:tag" content="编译原理">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://imgbed.cheney.cc/picgo/20210511114109555-20220405205526898.png">
  
  
  <title>编译原理复习总结（精华版） - Cheney blog</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4/github-markdown.min.css" />
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hint.css@2/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.css" />
  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"cheney822.gitee.io","root":"/","version":"1.8.14","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":1},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>Cheney Blog</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              &nbsp;<i class="iconfont icon-search"></i>&nbsp;
            </a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('https://imgbed.cheney.cc/Blog_config/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="编译原理复习总结（精华版）">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-05-09 08:22" pubdate>
        2021年5月9日 早上
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      5.4k 字
    </span>
  

  
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      28 分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">编译原理复习总结（精华版）</h1>
            
            <div class="markdown-body">
              <blockquote>
<p>本文创作过程中参考了网上多篇文章，如有侵权，请联系作者删除</p>
</blockquote>
<blockquote>
<p>笔记分两部分：<br>——第一部分是一些小知识点<br>——第二部分对应了几个大题的解题模板</p>
</blockquote>
<h1 id="第一部分"><a href="#第一部分" class="headerlink" title="第一部分"></a>第一部分</h1><blockquote>
<p>这部分没什么体系，比较零碎，只记录了我感觉比较重要的部分知识点，大部分是一些容易混淆知识点的辨析</p>
</blockquote>
<ul>
<li>二义文法：对一部文法，如果至少存在一个句子，有两棵不同语法树，称该句子是二义性的，包含二义性的句子的文法称为二义文法。上下文无关文法是否具有二义性是不可判定的。但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是先天无二义性的</li>
<li>NFA和DFA的主要区别在于：1）DFA没有输入空串之上的转换动作。2）对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集。DFA：只有唯一初态。NFA：有初态集。DFA是NFA的特例。</li>
<li>分析方法分两大类：自上而下分析法和自下而上分析法 即推导与归约，最右推导是规范推导，逆过程为规范规约<br>自上而下语法分析是从G的开始符号S出发，通过反复使用产生式句型中的非终结符进行替换，逐步推导出源程序串，是一种产生的方法，面向目标的方法<br>自下而上语法分析从输入串开始不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替之，逐步归约到S，是一种辨认的方法，基于目标的方法</li>
<li>短语，直接短语，句柄，素短语，最左素短语：（这里给出在语法树上的直观区别方法）<br>—短语：在语法树中表示所有分支结点对应子树，短语即子树叶子对应的符号。注： 子树包括语法树本身，及句型本身也可以称为短语<br>—直接短语：在语法树中表示为该短语只有上下相邻父子两代<br>—句柄：最左直接短语<br>—素短语：指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语<br>—最左素短语：最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象</li>
</ul>
<blockquote>
<p>例如：G[T]:<br>T → T<em>F|F<br>F → F↑P|P<br>P → (T)|i<br>求给定句型：T</em>P↑(T*F)的短语，直接短语，句柄，素短语，最左素短语</p>
</blockquote>
<blockquote>
<p>步骤：<br>1.根据产生式做推导<br>2.根据推导画出语法树<br>3.根据语法树和以上规则得答案</p>
<p>—短语 5 个     P，T* F，(T* F)，P↑(T* F)，T<em>P↑(T</em> F)<br>—直接短语 2 个     P，T* F<br>—句柄     P<br>—素短语    T* F<br>—最左素短语    T* F</p>
</blockquote>
<ul>
<li><p>关于：LR(0)、SLR、LR、LALR<br>—区别：<br>—判断方法：</p>
</li>
<li><p>翻译程序、编译程序、解释程序<br>翻译程序：将用某种语言编写的程序转换成另一种语言形式的程序的程序<br>编译程序：用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。<br>解释程序：解释程序是高级语言翻译程序的一种，他将输入的源程序作为输入，解释一句后就提交给计算机执行一句，源程序命令被逐个直接解释执行</p>
</li>
<li><p>算符文法与算符优先文法:<br>算符文法：任一产生式的右部都不含两个连续非终结符的文法<br>算符优先文法：是不含空字符且对任一对终结符都有确定的&gt;&lt;=关系的算符文法</p>
</li>
<li><p>字母表：元素的非空有穷集合<br>符号：字母表中的元素<br>符号串：字母表中符号组成的有穷序列</p>
</li>
<li><p>句子、句型、语言<br>句型是由识别符Z推导而得的符号串<br>句子是没有非终结符号的句型<br>语言是句子的集合</p>
</li>
<li><p>中间代码形式：常见的有逆波兰记号、三元式、四元式和树<br>1.逆波兰（也称后缀表示）：没有括号，易于计算机处理<br>2.三元式（运算符，对象1，对象2）：不便于优化但间接三元式，可以克服这个缺点<br>3.树形表示 三元式表示也可用相应的树形表示<br>4.四元式：（运算符; 对象1，对象2, 结果）：有利于代码优化</p>
</li>
</ul>
<h1 id="第二部分"><a href="#第二部分" class="headerlink" title="第二部分"></a>第二部分</h1><blockquote>
<p>这部分对应几个大题的内容，每个部分也都可以通过编程来实现</p>
</blockquote>
<h2 id="一：根据正则表达式写出对应的最小化的DFA"><a href="#一：根据正则表达式写出对应的最小化的DFA" class="headerlink" title="一：根据正则表达式写出对应的最小化的DFA"></a>一：根据正则表达式写出对应的最小化的DFA</h2><h3 id="１-正则表达式转NFA：（语法制导）"><a href="#１-正则表达式转NFA：（语法制导）" class="headerlink" title="１.正则表达式转NFA：（语法制导）"></a>１.正则表达式转NFA：（语法制导）</h3><h3 id="２-NFA确定化（转DFA）：（子集法）"><a href="#２-NFA确定化（转DFA）：（子集法）" class="headerlink" title="２.NFA确定化（转DFA）：（子集法）"></a>２.NFA确定化（转DFA）：（子集法）</h3><p>首先了解两种运算：</p>
<blockquote>
<ol>
<li>ε-closure（I）：定义为一个状态集，是状态集I中的任何状态S经任意条 ε弧能够到达的状态的集合。</li>
<li>move（I，a）：定义为状态集合J，其中J是所有那些可以从I中某一状态经过一条a弧到达的状态的全体。</li>
</ol>
</blockquote>
<p>子集法步骤：<br>1.做一张表：</p>
<table>
<thead>
<tr>
<th></th>
<th></th>
<th></th>
</tr>
</thead>
<tbody><tr>
<td></td>
<td></td>
<td></td>
</tr>
</tbody></table>
<h3 id="３-DFA最小化（化简）：（分割法）"><a href="#３-DFA最小化（化简）：（分割法）" class="headerlink" title="３.DFA最小化（化简）：（分割法）"></a>３.DFA最小化（化简）：（分割法）</h3><p><strong>第一步：消除无用状态：</strong><br>无用状态：</p>
<blockquote>
<ul>
<li>不可达，孤立的点 即任何输入都不可到达。</li>
<li>无法到达终态的状态</li>
</ul>
</blockquote>
<p> 对于无用状态，可以非常简单的消去。</p>
<p><strong>第二步：合并等价状态（分割法）：</strong><br>等价状态：</p>
<blockquote>
<ul>
<li>来源一致：必须同时为可接受或者不可接受状态</li>
<li>去向一致：对所有的输入必须转换到等价的状态里面</li>
</ul>
</blockquote>
<p><strong>分割法步骤</strong></p>
<ul>
<li>1.首先将M的状态分为两个子集：一个由终态（可接受态）组成，另一个由非终态(包含初态)组成。</li>
<li>2.观察每个子集中的状态读取不同符号后，会不会转换到不同子集中的状态（去向不一致说明不等价）若能则将该子集分割成新的小的子集（按照去向的不同）</li>
<li>3.重复2，直至所有子集中的状态接收任何符号都无法再做分割为止，此时每个集合内部的状态都是等价的，将其合并并改写DFA即可。</li>
</ul>
<h3 id="下面是一个例题"><a href="#下面是一个例题" class="headerlink" title="下面是一个例题"></a>下面是一个例题</h3><p><img src="https://imgbed.cheney.cc/picgo/20210511114109555-20220405205526898.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p><img src="https://imgbed.cheney.cc/picgo/20210511114126577-20220405205526972.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h2 id="二：判断给定文法是不是LL（１）的，若是，则给出预测分析表并给出识别输入串的过程。"><a href="#二：判断给定文法是不是LL（１）的，若是，则给出预测分析表并给出识别输入串的过程。" class="headerlink" title="二：判断给定文法是不是LL（１）的，若是，则给出预测分析表并给出识别输入串的过程。"></a>二：判断给定文法是不是LL（１）的，若是，则给出预测分析表并给出识别输入串的过程。</h2><h3 id="１-消除左递归"><a href="#１-消除左递归" class="headerlink" title="１.消除左递归"></a>１.消除左递归</h3><ul>
<li>第一步：将间接左递归变为直接左递归<br>方法：类似中学用过的带入消元法，即通过产生式非终结符的替换，将将间接左递归变为直接左递归。</li>
<li>注意实际操作时需要指定一定的替换顺序</li>
<li>第二步：消除直接左递归<br>方法：直接左递归的形式为：A→A α1 |A α 2  |…|A α m |β 1 |β 2 |…|β n<br>消除左递归后改写为：<br>A→β 1 A’|β 2 A’|…| β n A’<br>A’→ α 1 A’| α 2 A’ | … | α m A’ | ε</li>
<li>例如：<br><img src="https://imgbed.cheney.cc/picgo/20210509210934937-20220405205527164.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></li>
</ul>
<h3 id="２-求出SELECT（需先求FIRST、FOLLOW）"><a href="#２-求出SELECT（需先求FIRST、FOLLOW）" class="headerlink" title="２.求出SELECT（需先求FIRST、FOLLOW）"></a>２.求出SELECT（需先求FIRST、FOLLOW）</h3><p>First(A)的含义指每个候选式的终结首符集；Follow(A)的含义指在文法G的一切句型中能够紧跟着A之后的一切终结符或#</p>
<h4 id="求非终结符表"><a href="#求非终结符表" class="headerlink" title="求非终结符表"></a>求非终结符表</h4><h4 id="求FIRST"><a href="#求FIRST" class="headerlink" title="求FIRST"></a>求FIRST</h4><ul>
<li>求非终结符A的FIRST集：<strong>检查每一个可以由A推出的产生式</strong></li>
<li>若产生式由终结符m开头（例如A -&gt;m），则直接将此非终结符m加入FIRST(A)集</li>
<li>若由非终结符B开头（例如A -&gt;BC），则再判断此非终结符B能推出空字符 ε<br>– 若不能：将此终结符B的FIRST（B）集合整体加入FIRST(A)集<br>– 若能：则将B的FIRST（B）集合整体除去 ε 加入FIRST(A)集，然后再次向处理B一样处理B之后的符号(这里是C)（相当于A吸收B中的空字符到达下一个符号）。</li>
</ul>
<h4 id="求FOLLOW"><a href="#求FOLLOW" class="headerlink" title="求FOLLOW"></a>求FOLLOW</h4><ul>
<li>求非终结符A的FOLLOW集：<strong>检查每一个可以推出A的产生式</strong></li>
<li>若A为文法的开始符号：将 # 加入FOLLOW（A）</li>
<li>若A为当前产生式的最后一个字符（例如B -&gt;CA）：将FOLLOW（B）加入FOLLOW（A）</li>
<li>若A后面还有其它字符例如（例如B-&gt;AD）：<br>– 如果D不能推出空字符 ε：将FIRST（D）加入FOLLOW（A）<br>– 如果D能够推出空字符 ε：将FIRST（D）减去 ε 加入FOLLOW（A）并且将FOLLOW（B）加入FOLLOW（A）</li>
</ul>
<h4 id="求SELECT"><a href="#求SELECT" class="headerlink" title="求SELECT"></a>求SELECT</h4><ul>
<li>SELECT ( A→α) =FIRST ( α ),其中α !⇒ ε<br>若α ⇒ε ，则SELECT ( A→α) = (FIRST（α ） － {ε ) ∪FOLLOW(A)</li>
<li>注意α在这里的是一个产生式，而不是一个符号</li>
</ul>
<h3 id="３-判断是否是LL（１）"><a href="#３-判断是否是LL（１）" class="headerlink" title="３.判断是否是LL（１）"></a>３.判断是否是LL（１）</h3><ul>
<li>对每个非终结符A的两个不同产生式，A→α ，A→β ，</li>
<li>满足SELECTC（A→α ）∩SELECT（A→β ）= ϕ</li>
<li>其中α、β不能同时⇒ ε</li>
<li>则称该文法是LL（１）的</li>
</ul>
<h3 id="４-构造预测分析表"><a href="#４-构造预测分析表" class="headerlink" title="４.构造预测分析表"></a>４.构造预测分析表</h3><p>预测分析表M 如下矩阵形式：矩阵M<br>•行标题用文法的非终结符表示。<br>•列标题用文法的终结符号和#表示。<br>•矩阵元素M[A, a]的内容是产生式A→α \alphaα（或→α \alphaα）表明当对A进行推导，面临输入符号a时，应采用候选α \alphaα进行推导。<br>出错处理标志（即表中空白项）表明A不该面临输入符号a。</p>
<h3 id="５-识别输入串的过程"><a href="#５-识别输入串的过程" class="headerlink" title="５.识别输入串的过程"></a>５.识别输入串的过程</h3><ul>
<li>总控程序：分析栈【存放分析过程中的文法符号】，分析表<br>总是按栈顶符号x和当前输入符号行事。</li>
<li>对于任何（x,a），总控程序每次都执行下述三种可能动作之一：<br>（a）若x=a=‘#’，则宣布分析成功。<br>（b）若x=a≠ ‘#’，则把x从栈顶逐出，指针指向下一输入符号。<br>（c）若x是一个非终结符，则查看分析表M。<br>①如果M[A, a]中存放关于X的一个产生式，那么，首先把X顶出栈，然后把产生式右部符号串按反序一一推进栈。<br>②如果M[A, a]中存放“出错标志”，则调用出错处理程序ERROR。</li>
</ul>
<h3 id="下面是一个例题-1"><a href="#下面是一个例题-1" class="headerlink" title="下面是一个例题"></a>下面是一个例题</h3><h4 id="消除左递归"><a href="#消除左递归" class="headerlink" title="消除左递归"></a>消除左递归</h4><p><img src="https://imgbed.cheney.cc/picgo/20210510080444695-20220405205527238.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h4 id="求FIRST、FOLLOW、SELECT并判断"><a href="#求FIRST、FOLLOW、SELECT并判断" class="headerlink" title="求FIRST、FOLLOW、SELECT并判断"></a>求FIRST、FOLLOW、SELECT并判断</h4><p><img src="https://imgbed.cheney.cc/picgo/20210510080500270-20220405205527394.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h4 id="构造预测分析表"><a href="#构造预测分析表" class="headerlink" title="构造预测分析表"></a>构造预测分析表</h4><p><img src="https://imgbed.cheney.cc/picgo/2021051008045345-20220405205527497.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h4 id="识别输入串"><a href="#识别输入串" class="headerlink" title="识别输入串"></a>识别输入串</h4><p><img src="https://imgbed.cheney.cc/picgo/20210510080511237-20220405205527622.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h2 id="三：构造给定文法的拓广文法的LR-0-项目集规范族，并给出识别活前缀的DFA，判断文法是LR-0-，SLR-１-，LALR-１-还是LR-１-的，构造相应的分析表。"><a href="#三：构造给定文法的拓广文法的LR-0-项目集规范族，并给出识别活前缀的DFA，判断文法是LR-0-，SLR-１-，LALR-１-还是LR-１-的，构造相应的分析表。" class="headerlink" title="三：构造给定文法的拓广文法的LR(0)项目集规范族，并给出识别活前缀的DFA，判断文法是LR(0)，SLR(１)，LALR(１)还是LR(１)的，构造相应的分析表。"></a>三：构造给定文法的拓广文法的LR(0)项目集规范族，并给出识别活前缀的DFA，判断文法是LR(0)，SLR(１)，LALR(１)还是LR(１)的，构造相应的分析表。</h2><h3 id="构造拓广文法"><a href="#构造拓广文法" class="headerlink" title="构造拓广文法"></a>构造拓广文法</h3><p>加个S’的规则就行。</p>
<blockquote>
<p>S’-&gt;E</p>
<p>E-&gt;aA | bB</p>
<p>A-&gt;cA | d</p>
<p>B-&gt;cB | d</p>
</blockquote>
<h3 id="构造LR-0-项目集规范族"><a href="#构造LR-0-项目集规范族" class="headerlink" title="构造LR(0)项目集规范族"></a>构造LR(0)项目集规范族</h3><h4 id="求文法的所有项目"><a href="#求文法的所有项目" class="headerlink" title="求文法的所有项目"></a>求文法的所有项目</h4><p>给每个规则加一个点以后然后挪位置，挪一个位置就得到一个项目</p>
<blockquote>
<p>1.S’-&gt;·E   2.S’-&gt;E·   3.E-&gt;·aA   4.E-&gt;a·A   5.E-&gt;aA·   6.A-&gt;·cA   7.A-&gt;c·A   8.A-&gt;cA·   9.A-&gt;·d</p>
<p>10.A-&gt;d·   11.E-&gt;·bB   12.E-&gt;b·B   13.E-&gt;bB·   14.B-&gt;·cB   15.B-&gt;c·B   16.B-&gt;cB·   17.B-&gt;·d   18.B-&gt;d·</p>
</blockquote>
<h4 id="项目集规范族"><a href="#项目集规范族" class="headerlink" title="项目集规范族"></a>项目集规范族</h4><p>把有S’的项目而且点在最左边的项目作为状态I0的核，放在开头。</p>
<blockquote>
<p>S’-&gt;·E<br>E-&gt;·aA<br>E-&gt;·bB</p>
</blockquote>
<p>然后看这个点后面的非终结符，是个E，接下来就去项目中找左部是E的而且点在最左边开头位置的项目，列在核的下面，这就是状态I0了，你可以画个框框然后标记一下。<br>接下来还是先看核里面点后的这个非终结符E，输入E（你可以理解为在箭弧上标了个E），把点向后移一位，得到S’-&gt;E·，这其实是得到了一个新的状态的核。当然另外两个也一样，输入点后面的符号，比如输入a得到E-&gt;a·A为核的新状态，输入b得到E-&gt;b·B为核的新状态。得到新状态的核了，就顺便把这个状态剩下的项目也列出来吧，就是看核的点后面的非终结符，找以这个非终结符为左部的点在最左边的项目。当然要是点后面没有东西就不用找了，新的状态记得标号哦。<br>是重复上面的工作，从每一个新状态出发，逐个输入每个项目点后面的符号，就是后移一位，又分别作为新的状态的核然后根据核找下面的同状态里的项目。找到找不动为止<br><img src="https://imgbed.cheney.cc/picgo/2021051309313828-20220405205527662.jpg" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h3 id="给出识别活前缀的DFA"><a href="#给出识别活前缀的DFA" class="headerlink" title="给出识别活前缀的DFA"></a>给出识别活前缀的DFA</h3><p>把文法的所有产生式的项目都列出来，并使每个项目都作为NFA的一个状态。</p>
<h3 id="判断文法类型"><a href="#判断文法类型" class="headerlink" title="判断文法类型"></a>判断文法类型</h3><ul>
<li>如果文法对应的自动机中不存在移进-归约冲突和归约-归约冲突则为 LR(0)文法</li>
</ul>
<h3 id="构造分析表：LR（０）"><a href="#构造分析表：LR（０）" class="headerlink" title="构造分析表：ＬＲ（０）"></a>构造分析表：ＬＲ（０）</h3><p>1、找项目集规范族有S’-&gt;A·这种形状的那个状态Ik，就是第k个状态，则把分析表第k行的#列标上acc</p>
<p>2、按顺序（我一般是按状态序号顺序）分析状态的项目和GOTO函数，主要就是看每个项目的点后面的符号。</p>
<p>（1）要是是个终结符，看输入这个终结符后去的哪个状态，比如当前是状态I0，对于第二个项目E-&gt;·aA，输入a以后去了状态I2，那就在分析表中第0行的a列写上S2，意思就是状态Ik输入Vt后去了Ij状态。</p>
<p>（2）要是是个非终结符，这个更好理解，比如从状态Ik输入这个非终结符以后去了状态Ij，那就在GOTO表的第k行第Vn列写j。</p>
<p>3、你会发现有的项目的点是在最后，这就是分析表里面那些小r的来历了。先看这个项目所在的状态，再看点前面的规则是文法里面的第几个规则，比如说状态I10的A-&gt;d·里面的A-&gt;d就是文法的第4条规则，那就在分析表的第10行所有的终结符列包括#列写上r4，就是ACTION列的一行写满。即状态Ik的项目来自于文法的第j条规则，则分析表的第k行都是rj。</p>
<h2 id="四：计算给定文法的FIRETVT和LASTVT，构造算符优先分析表并说明文法是否是算符优先文法。"><a href="#四：计算给定文法的FIRETVT和LASTVT，构造算符优先分析表并说明文法是否是算符优先文法。" class="headerlink" title="四：计算给定文法的FIRETVT和LASTVT，构造算符优先分析表并说明文法是否是算符优先文法。"></a>四：计算给定文法的FIRETVT和LASTVT，构造算符优先分析表并说明文法是否是算符优先文法。</h2><h3 id="计算FIRETVT和LASTVT"><a href="#计算FIRETVT和LASTVT" class="headerlink" title="计算FIRETVT和LASTVT"></a>计算FIRETVT和LASTVT</h3><ul>
<li>FIRSTVT(B) = {b| B=&gt;b… 或 B=&gt;Cb…}</li>
</ul>
<blockquote>
<p>规则：<br>若B-&gt;b… 或 B-&gt;Cb… 则b加入FIRSTVT(B)<br>若B-&gt;A… 则FIRSTVT(A) 加入FIRSTVT(B) </p>
</blockquote>
<ul>
<li>LASTVT(B) = {a| B=&gt;…a 或 B=&gt;…aC}</li>
</ul>
<blockquote>
<p>规则：<br>若B=&gt;…a 或 B=&gt;…aC 则a加入LASTVT(B)<br>若B-&gt;…A 则LASTVT(A) 加入LASTVT(B)</p>
</blockquote>
<h3 id="构造算符优先分析表"><a href="#构造算符优先分析表" class="headerlink" title="构造算符优先分析表"></a>构造算符优先分析表</h3><ul>
<li>算符优先分析表M 如下矩阵形式：<br>•行标题用文法的终结符和#表示。<br>•列标题用文法的终结符和#表示。<br>•表中的元素为&gt;&lt;=或空四者之一。</li>
<li>首先填写表中的=项：<br>若文法中产生式有满足P-&gt;…ab…或P-&gt;…aQb…的那么就直接填写=，注意顺序是左边等于右边，对应表是横着的等于竖着的，这里是（=），#号直接填写等于就好了。</li>
</ul>
<ul>
<li>然后是&gt;和&lt;<br>找类似于P-&gt;QaR这种有用的文法，终结符和非终结符在一起的那种。找到后根据以下两条：<br>1.a小于FIRSTVT(R）中元素，横着写<br>2.LASTVT（Q）中元素大于a，竖着写</li>
</ul>
<h3 id="判断文法是否算符优先文法"><a href="#判断文法是否算符优先文法" class="headerlink" title="判断文法是否算符优先文法"></a>判断文法是否算符优先文法</h3><p>判断标准：文法任一产生式右部都不含两个相继的非终结符为算符文法。<br>方法：利用上述得到的分析表，若两个终结符之间至多满足=，&lt;，&gt;，三种关系之一（一个表格内部只填写一个符号），可以判断该文法为算符优先文法，反之不是。</p>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%9F%BA%E7%A1%80/">计算机基础</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AC%94%E8%AE%B0/">笔记</a>
                    
                      <a class="hover-with-bg" href="/tags/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86/">编译原理</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/05/09/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F__%E8%87%AA%E5%88%B6%E7%AE%80%E5%8D%95U%E7%9B%98%E5%BC%95%E5%AF%BC%E7%A8%8B%E5%BA%8F/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">自制简单U盘引导程序.md</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2021/05/08/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F__Linux%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F%E5%AE%9E%E9%AA%8C%EF%BC%88C%E8%AF%AD%E8%A8%80%E5%AE%9E%E7%8E%B0%E6%96%B0%E5%BB%BA%E3%80%81%E6%89%93%E5%BC%80%E3%80%81%E5%85%B3%E9%97%AD%E3%80%81%E8%AF%BB%E5%86%99%E6%96%87%E4%BB%B6%E4%BB%A5%E5%8F%8A%E6%9F%A5%E6%94%B9%E6%96%87%E4%BB%B6%E6%9D%83%E9%99%90%EF%BC%89/">
                        <span class="hidden-mobile">Linux文件系统实验（C语言实现新建、打开、关闭、读写文件以及查改文件权限）</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://cheney822.gitee.io/" target="_blank" rel="nofollow noopener"><span>备用网址</span></a> 
  </div>
  

  
  <!-- 备案信息 -->
  <div class="beian">
    <span>
      <a href="http://beian.miit.gov.cn/" target="_blank" rel="nofollow noopener">
        皖ICP备2022002876号-1
      </a>
    </span>
    
  </div>


  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  <script  src="/js/local-search.js" ></script>



  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  
    <script  src="https://cdn.jsdelivr.net/npm/tocbot@4/dist/tocbot.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4/anchor.min.js" ></script>
  
  
    <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js" ></script>
  






  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
        typing(title);
      
    })(window, document);
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
